{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #志愿者调配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: volunteerDeployment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #志愿者调配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "「力扣挑战赛」有 `n` 个比赛场馆（场馆编号从 `0` 开始），场馆之间的通道分布情况记录于二维数组 `edges` 中，`edges[i]= [x, y]` 表示第 `i` 条通道连接场馆 `x` 和场馆 `y`(即两个场馆相邻)。初始每个场馆中都有一定人数的志愿者（不同场馆人数可能不同），后续 `m` 天每天均会根据赛事热度进行志愿者人数调配。调配方案分为如下三种：\n",
    "1. 将编号为 `idx` 的场馆内的志愿者人数减半；\n",
    "2. 将编号为 `idx` 的场馆相邻的场馆的志愿者人数都加上编号为 `idx` 的场馆的志愿者人数；\n",
    "3. 将编号为 `idx` 的场馆相邻的场馆的志愿者人数都减去编号为 `idx` 的场馆的志愿者人数。\n",
    "\n",
    "所有的调配信息记录于数组 `plans` 中，`plans[i] = [num,idx]` 表示第 `i` 天对编号 `idx` 的场馆执行了第 `num` 种调配方案。\n",
    "在比赛结束后对调配方案进行复盘时，不慎将第 `0` 个场馆的**最终**志愿者人数丢失，只保留了**初始**所有场馆的志愿者总人数 `totalNum` ，以及记录了第 `1 ~ n-1` 个场馆的**最终**志愿者人数的一维数组 `finalCnt`。请你根据现有的信息求出初始每个场馆的志愿者人数，并按场馆编号顺序返回志愿者人数列表。\n",
    "\n",
    "**注意：**\n",
    "- 测试数据保证当某场馆进行第一种调配时，该场馆的志愿者人数一定为偶数；\n",
    "- 测试数据保证当某场馆进行第三种调配时，该场馆的相邻场馆志愿者人数不为负数；\n",
    "- 测试数据保证比赛开始时每个场馆的志愿者人数都不超过 `10^9`；\n",
    "- 测试数据保证给定的场馆间的道路分布情况中不会出现自环、重边的情况。\n",
    "\n",
    "\n",
    "**示例 1：**\n",
    ">![image.png](https://pic.leetcode-cn.com/1630061228-gnZsOz-image.png)\n",
    "> 输入：\n",
    ">`finalCnt = [1,16], totalNum = 21, edges = [[0,1],[1,2]], plans = [[2,1],[1,0],[3,0]]`\n",
    ">\n",
    "> 输出：`[5,7,9]`\n",
    ">\n",
    "> 解释：\n",
    "> ![image.png](https://pic.leetcode-cn.com/1630061300-WuVkeF-image.png){:height=200}\n",
    "\n",
    "\n",
    "**示例 2 ：**\n",
    "> 输入：\n",
    ">`finalCnt = [4,13,4,3,8], totalNum = 54, edges = [[0,3],[1,3],[4,3],[2,3],[2,5]], plans = [[1,1],[3,3],[2,5],[1,0]]`\n",
    ">\n",
    "> 输出：`[10,16,9,4,7,8]`\n",
    "\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `2 <= n <= 5*10^4`\n",
    "- `1 <= edges.length <= min((n * (n - 1)) / 2, 5*10^4)`\n",
    "- `0 <= edges[i][0], edges[i][1] < n`\n",
    "- `1 <= plans.length <= 10`\n",
    "- `1 <= plans[i][0] <=3`\n",
    "- `0 <= plans[i][1] < n`\n",
    "- `finalCnt.length = n-1`\n",
    "- `0 <= finalCnt[i] < 10^9`\n",
    "- `0 <= totalNum < 5*10^13`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [05ZEDJ](https://leetcode.cn/problems/05ZEDJ/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [05ZEDJ](https://leetcode.cn/problems/05ZEDJ/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,16]\\n21\\n[[0,1],[1,2]]\\n[[2,1],[1,0],[3,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        finalCnt.insert(0,0)\n",
    "        n = len(finalCnt)\n",
    "        x = [0] * n\n",
    "        x[0] = 1\n",
    "        adj = [list() for i in range(n)]\n",
    "        for u,v in edges:\n",
    "            adj[u].append(v)\n",
    "            adj[v].append(u)\n",
    "        for num,idx in plans[::-1]:\n",
    "            if num == 1:\n",
    "                finalCnt[idx] *= 2\n",
    "                x[idx] *= 2\n",
    "            elif num == 2:\n",
    "                for v in adj[idx]:\n",
    "                    finalCnt[v] -= finalCnt[idx]\n",
    "                    x[v] -= x[idx]\n",
    "            else:\n",
    "                for v in adj[idx]:\n",
    "                    finalCnt[v] += finalCnt[idx]\n",
    "                    x[v] += x[idx]\n",
    "        zero_end = (totalNum - sum(finalCnt)) // sum(x)\n",
    "        for i in range(n):\n",
    "            finalCnt[i] += x[i] * zero_end\n",
    "        return finalCnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        n = len(finalCnt) + 1\n",
    "        g = [[] for _ in range(n)]  # 建图\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        # final count of all n vertices\n",
    "        # initialize the final count of vertice 0 as complex number 1j\n",
    "        cnt = [0+1j] + finalCnt\n",
    "\n",
    "        # reverse simulation\n",
    "        for num, idx in plans[::-1]:\n",
    "            # option1: halve the number of volunteers\n",
    "            if num == 1:\n",
    "                cnt[idx] *= 2\n",
    "            # option2: adding the number of volunteers\n",
    "            elif num == 2:\n",
    "                for neighbor in g[idx]:\n",
    "                    cnt[neighbor] -= cnt[idx]\n",
    "            # option3: substracting the number of volunteers\n",
    "            else:\n",
    "                for neighbor in g[idx]:\n",
    "                    cnt[neighbor] += cnt[idx]\n",
    "        \n",
    "        s = sum(cnt)\n",
    "\n",
    "        # initial number of volunteers at vertex 0\n",
    "        initial0 = (totalNum - s.real) // s.imag\n",
    "\n",
    "        # final number of volunteers at each vertex\n",
    "        ans = [int(x.real + x.imag * initial0) for x in cnt]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        firstNumList = [1] + [0] * len(finalCnt)\n",
    "        originCnt = [0] + finalCnt\n",
    "        table = [[] for _ in range(len(firstNumList))]\n",
    "        plan_fun = []\n",
    "        def method1(idx):\n",
    "            originCnt[idx] *= 2\n",
    "            firstNumList[idx] *= 2\n",
    "        def method2(idx):\n",
    "            for i in table[idx]:\n",
    "                originCnt[i] -= originCnt[idx]\n",
    "                firstNumList[i] -= firstNumList[idx]\n",
    "        def method3(idx):\n",
    "            for i in table[idx]:\n",
    "                originCnt[i] += originCnt[idx]\n",
    "                firstNumList[i] += firstNumList[idx]\n",
    "        plan_fun = (0, method1, method2, method3)\n",
    "        for edge in edges:\n",
    "            table[edge[0]].append(edge[1])\n",
    "            table[edge[1]].append(edge[0])\n",
    "        for i in range(len(plans) - 1, -1, -1):\n",
    "            plan = plans[i]\n",
    "            plan_fun[plan[0]](plan[1])\n",
    "        rate = sum(firstNumList)\n",
    "        first_num = (totalNum - sum(originCnt)) // rate\n",
    "        for i in range(len(originCnt)):\n",
    "            originCnt[i] += firstNumList[i] * first_num\n",
    "        return originCnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        fn = [1] + [0]*len(finalCnt)\n",
    "        finalCnt = [0]+finalCnt\n",
    "        # 初始化两个数组\n",
    "        # 操作均为线性\n",
    "        dic=collections.defaultdict(list)\n",
    "        for e in edges:\n",
    "            u,v=e[0],e[1]\n",
    "            dic[u].append(v)\n",
    "            dic[v].append(u)\n",
    "        # 建立场馆之间的连接\n",
    "        for i in range(len(plans)-1,-1,-1):\n",
    "            num = plans[i][0]\n",
    "            ids = plans[i][1]\n",
    "            arr = dic[ids]\n",
    "            if num == 3:\n",
    "                for j in arr:\n",
    "                    fn[j]+=fn[ids]\n",
    "                    finalCnt[j]+=finalCnt[ids]\n",
    "            elif num == 2:\n",
    "                for j in arr:\n",
    "                    fn[j]-=fn[ids]\n",
    "                    finalCnt[j]-=finalCnt[ids]\n",
    "            else:\n",
    "                fn[ids]*=2\n",
    "                finalCnt[ids]*=2\n",
    "        fnsum = sum(fn)\n",
    "        finalCntsum = sum(finalCnt)\n",
    "        for i in range(len(finalCnt)):\n",
    "            finalCnt[i] += fn[i]*((totalNum-finalCntsum)//fnsum)\n",
    "        return finalCnt\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        dc, finalCnt = defaultdict(list), [1j] + finalCnt\n",
    "        for i,j in edges:\n",
    "            dc[i].append(j)\n",
    "            dc[j].append(i)\n",
    "        for i,j in plans[::-1]:\n",
    "            v = finalCnt[j]\n",
    "            if i==1: finalCnt[j] *= 2\n",
    "            elif i==2:\n",
    "                for k in dc[j]: finalCnt[k] -= v\n",
    "            else:\n",
    "                for k in dc[j]: finalCnt[k] += v\n",
    "        sm = sum(finalCnt)\n",
    "        i = ((totalNum - sm.real) // sm.imag) if sm.imag else 0\n",
    "        return [int(x.real + x.imag * i) for x in finalCnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        changshu = [0] +finalCnt\n",
    "        xishu = [0] * (len(finalCnt)+1)\n",
    "        xishu[0] = 1\n",
    "        tu = collections.defaultdict(list)\n",
    "        for i in edges:\n",
    "            tu[i[1]].append(i[0])\n",
    "            tu[i[0]].append(i[1])\n",
    "\n",
    "        while plans:\n",
    "            caozuo,idx = plans.pop()\n",
    "            if caozuo == 1:\n",
    "                changshu[idx]*= 2\n",
    "                xishu[idx]*= 2\n",
    "            elif caozuo == 2:\n",
    "                for i in tu[idx]:\n",
    "                    changshu[i]-= changshu[idx]\n",
    "                    xishu[i]-= xishu[idx]\n",
    "            else:\n",
    "                for i in tu[idx]:\n",
    "                    changshu[i]+= changshu[idx]\n",
    "                    xishu[i]+= xishu[idx]\n",
    "\n",
    "\n",
    "        A = sum(xishu)\n",
    "        B = sum(changshu)\n",
    "        x = (totalNum-B)/A \n",
    "        ans = [0] * (len(finalCnt)+1)\n",
    "        for i in range(len(ans)):\n",
    "            ans[i] = int(xishu[i]*x + changshu[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        n = len(finalCnt)+1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        # 记录其他节点包含多少个节点0的x值，然后解方程\n",
    "        # 设最后0节点的人数是x\n",
    "        rec = [[finalCnt[i], 0] for i in range(n-1)]\n",
    "        rec = [[0, 1]] + rec\n",
    "        # 然后是根据plans逆过程，求出最初的rec情况\n",
    "        for i in range(len(plans)-1, -1, -1):\n",
    "            num, idx = plans[i]\n",
    "            if num==1:\n",
    "                rec[idx][0]*=2\n",
    "                rec[idx][1]*=2\n",
    "            elif num==2:\n",
    "                for y in g[idx]:\n",
    "                    rec[y][0] -= rec[idx][0]\n",
    "                    rec[y][1] -= rec[idx][1]\n",
    "            else:\n",
    "                for y in g[idx]:\n",
    "                    rec[y][0] += rec[idx][0]\n",
    "                    rec[y][1] += rec[idx][1]\n",
    "        \n",
    "        total = 0\n",
    "        x_num = 0\n",
    "        for val, x_cot in rec:\n",
    "            total += val\n",
    "            x_num += x_cot\n",
    "        \n",
    "        x = (totalNum - total)//x_num\n",
    "        res = [val+cot*x for val, cot in rec]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        n = len(finalCnt) + 1\n",
    "        vol = [[0] * 2 for _ in range(n)]\n",
    "        vol[0][0], vol[0][1] = 1, 0\n",
    "        for i in range(n - 1):\n",
    "            vol[i + 1][0], vol[i + 1][1] = 0, finalCnt[i]\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            neighbors[i].append(j)\n",
    "            neighbors[j].append(i)\n",
    "        m = len(plans)\n",
    "        for j in range(m - 1, -1, -1):\n",
    "            num, idx = plans[j][0], plans[j][1]\n",
    "            if num == 1:\n",
    "                vol[idx][0] *= 2\n",
    "                vol[idx][1] *= 2\n",
    "            elif num == 2:\n",
    "                for i in neighbors[idx]:\n",
    "                    vol[i][0] -= vol[idx][0]\n",
    "                    vol[i][1] -= vol[idx][1]\n",
    "            else:\n",
    "                for i in neighbors[idx]:\n",
    "                    vol[i][0] += vol[idx][0]\n",
    "                    vol[i][1] += vol[idx][1]\n",
    "        a, b = 0, 0\n",
    "        for i, j in vol:\n",
    "            a += i\n",
    "            b += j\n",
    "        x = round((totalNum - b) / a)\n",
    "        ans = [round(vol[i][0] * x + vol[i][1]) for i in range(n)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        peers = {}\n",
    "        for x,y in edges:\n",
    "            if x not in peers:\n",
    "                peers[x] = [y]\n",
    "            else:\n",
    "                peers[x].append(y)\n",
    "\n",
    "            if y not in peers:\n",
    "                peers[y] = [x]\n",
    "            else:\n",
    "                peers[y].append(x)\n",
    "        counts = [[1, 0]]\n",
    "        counts.extend([[0, c] for c in finalCnt])\n",
    "        for num, idx in plans[::-1]:\n",
    "            if num == 1:\n",
    "                counts[idx][0] *= 2\n",
    "                counts[idx][1] *= 2\n",
    "            elif idx not in peers:\n",
    "                continue\n",
    "            elif num == 2:\n",
    "                for peer in peers[idx]:\n",
    "                    counts[peer][0] -= counts[idx][0]\n",
    "                    counts[peer][1] -= counts[idx][1]\n",
    "            else:\n",
    "                for peer in peers[idx]:\n",
    "                    counts[peer][0] += counts[idx][0]\n",
    "                    counts[peer][1] += counts[idx][1]\n",
    "        nx = 0\n",
    "        cc = 0\n",
    "        for x, c in counts:\n",
    "            nx += x\n",
    "            cc += c\n",
    "        x = (totalNum - cc) // nx\n",
    "        return [n*x+c for n,c in counts]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        finalCnt = [[1, 0]] + [[0, x] for x in finalCnt]\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges: \n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        for num, idx in plans[::-1]:\n",
    "            if num == 1:\n",
    "                finalCnt[idx][0] *= 2\n",
    "                finalCnt[idx][1] *= 2\n",
    "            if num == 2:\n",
    "                for x in g[idx]: \n",
    "                    finalCnt[x][0] -= finalCnt[idx][0]\n",
    "                    finalCnt[x][1] -= finalCnt[idx][1]\n",
    "            if num == 3: \n",
    "                for x in g[idx]:\n",
    "                    finalCnt[x][0] += finalCnt[idx][0]\n",
    "                    finalCnt[x][1] += finalCnt[idx][1]\n",
    "        c = 0\n",
    "        for x, y in finalCnt:\n",
    "            c += x\n",
    "            totalNum -= y\n",
    "        un = totalNum // c\n",
    " \n",
    "        return [x * un + y for x, y in finalCnt]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        N = 10 ** 15\n",
    "        finalCnt = [N] + finalCnt\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges: \n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        for num, idx in plans[::-1]:\n",
    "            if num == 1:\n",
    "                finalCnt[idx] *= 2\n",
    "            if num == 2:\n",
    "                for x in g[idx]: finalCnt[x] -= finalCnt[idx]\n",
    "            if num == 3: \n",
    "                for x in g[idx]: finalCnt[x] += finalCnt[idx]\n",
    "        ans = []\n",
    "\n",
    "        c = 0\n",
    "        for x in finalCnt:\n",
    "            c0 = x // N\n",
    "            t = x % N\n",
    "            if t > 10 ** 14:\n",
    "                c0 += 1\n",
    "                t -= N\n",
    "            c += c0\n",
    "            ans.append((c0, t))\n",
    "            totalNum -= t\n",
    "        \n",
    "        print(finalCnt)\n",
    "        print(ans)\n",
    "        un = totalNum // c\n",
    "        print(un)\n",
    "        \n",
    "        return [x * un + y for x, y in ans]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        def f1(edge, number, idx):\n",
    "            number[idx][0] *= 2\n",
    "            number[idx][1] *= 2\n",
    "            # if idx == 0:\n",
    "            #     number[idx][0] *= 2\n",
    "            # else:\n",
    "            #     number[idx][1] *= 2\n",
    "        \n",
    "        def f2(edge, number, idx):\n",
    "            nodes = edge[idx]\n",
    "            for node in nodes:\n",
    "                number[node][0] -= number[idx][0]\n",
    "                number[node][1] -= number[idx][1]\n",
    "            # if idx == 0:\n",
    "            #     for node in nodes:\n",
    "            #         number[node][0] += number[idx][0]\n",
    "            #         number[node][1] += number[idx][1]\n",
    "            # else:\n",
    "       \n",
    "        def f3(edge, number, idx):\n",
    "            nodes = edge[idx]\n",
    "            for node in nodes:\n",
    "                number[node][0] += number[idx][0]\n",
    "                number[node][1] += number[idx][1]\n",
    "        \n",
    "        edge = defaultdict(list)\n",
    "        for e in edges:\n",
    "            edge[e[0]].append(e[1])\n",
    "            edge[e[1]].append(e[0])\n",
    "        number = defaultdict(list)\n",
    "        number[0] = [1, 0]\n",
    "        for idx, cnt in enumerate(finalCnt):\n",
    "            number[idx+1] = [0, cnt]\n",
    "        \n",
    "        for plan in plans[::-1]:\n",
    "            if plan[0] == 1:\n",
    "                f1(edge, number, plan[1])\n",
    "                continue\n",
    "            if plan[0] == 2:\n",
    "                f2(edge, number, plan[1])\n",
    "                continue\n",
    "            if plan[0] == 3:\n",
    "                f3(edge, number, plan[1])\n",
    "                continue\n",
    "            \n",
    "        # x = (totalNum - sum([num[1] for num in number])) // (sum([num[0] for num in number]))\n",
    "        x = (totalNum - sum([num[1] for num in number.values()])) // sum([num[0] for num in number.values()])\n",
    "        res = []\n",
    "        for num in number.values():\n",
    "            res.append(num[0] * x+ num[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        # x , 1, 16 ---------- f(x) = 21\n",
    "        # 2*x-(1+x) , 1+x,16-(1+x)-----x+15==21\n",
    "        # 多项式系数?\n",
    "        # (1,0) (0,1) (0,16)\n",
    "        # 3:对附近的加上自身 2:对附近的减去自身 1:使自身翻倍\n",
    "        # finalCnt----(1,0) (0, finalCnt[0]) ... (0, finalCnt[-1])\n",
    "        d=defaultdict(set)\n",
    "        start=[(1,0)]+[(0,c) for c in finalCnt]\n",
    "        for x,y in edges:\n",
    "            d[x].add(y)\n",
    "            d[y].add(x)\n",
    "        for op, idx in reversed(plans):\n",
    "            if op==1:\n",
    "                start[idx]=tuple([2*c for c in start[idx]])\n",
    "            if op==2:\n",
    "                for p in d[idx]:\n",
    "                    start[p]=tuple([start[p][i]-start[idx][i] for i in range(2)])\n",
    "            if op==3:\n",
    "                for p in d[idx]:\n",
    "                    start[p]=tuple([start[p][i]+start[idx][i] for i in range(2)])\n",
    "        s=(0,0)\n",
    "        for p in start:\n",
    "            s=tuple([s[i]+p[i] for i in range(2)])\n",
    "        xx = (totalNum - s[1])//s[0]\n",
    "        return [c[0]*xx+c[1] for c in start]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def volunteerDeployment(self, finalCnt: List[int], totalNum: int, edges: List[List[int]], plans: List[List[int]]) -> List[int]:\n",
    "        # x , 1, 16 ---------- f(x) = 21\n",
    "        # 2*x-(1+x) , 1+x,16-(1+x)-----x+15==21\n",
    "        # 多项式系数?\n",
    "        # (1,0) (0,1) (0,16)\n",
    "        # 3:对附近的加上自身 2:对附近的减去自身 1:使自身翻倍\n",
    "        # finalCnt----(1,0) (0, finalCnt[0]) ... (0, finalCnt[-1])\n",
    "        d=defaultdict(set)\n",
    "        start=[(1,0)]+[(0,c) for c in finalCnt]\n",
    "        for x,y in edges:\n",
    "            d[x].add(y)\n",
    "            d[y].add(x)\n",
    "        for op, idx in reversed(plans):\n",
    "            if op==1:\n",
    "                start[idx]=tuple([2*c for c in start[idx]])\n",
    "            if op==2:\n",
    "                for p in d[idx]:\n",
    "                    start[p]=tuple([start[p][i]-start[idx][i] for i in range(2)])\n",
    "            if op==3:\n",
    "                for p in d[idx]:\n",
    "                    start[p]=tuple([start[p][i]+start[idx][i] for i in range(2)])\n",
    "        s=(0,0)\n",
    "        for p in start:\n",
    "            s=tuple([s[i]+p[i] for i in range(2)])\n",
    "        xx = (totalNum - s[1])//s[0]\n",
    "        return [c[0]*xx+c[1] for c in start]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
